package com.work.daily;

/**
 * 给定一个二叉树，找出其最大深度。
 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
 说明: 叶子节点是指没有子节点的节点
 示例：
 给定二叉树 [3,9,20,null,null,15,7]

 方法一. 深度优先遍历法 DFS

 * Created by suk on 2020/8/25.
 */
public class MaxDepth_104_01 {

    public static void main(String[] args) {
        System.out.println(maxDepth(null));
    }
    public static int maxDepth(TreeNode root) {

        if (root == null) return 0;
        // 左子树高度
        int leftHeight = maxDepth(root.left);
        // 右子树高度
        int rightHeight = maxDepth(root.right);
        return Math.max(leftHeight, rightHeight) + 1;
    }

    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            val = x;
        }

    }
}
